// https://leetcode.cn/problems/maximum-product-subarray/
// Created by ade on 2022/8/19.
//
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 最笨的方法，以0为分隔点 分开计算
    int maxProduct1(vector<int> &nums) {
        int maxN = nums[0];
        vector<int> tmp = {};
        int zeroNums = 0;
        for (auto i : nums) {
            if (i == 0) {
                if (tmp.size() == 0) continue;
                maxN = max(maxN, i);
                int tmpMax = 1;
                if (zeroNums % 2 == 1) {
                    for (int j = 0; j < tmp.size(); j++) {
                        tmpMax *= tmp[j];
                        maxN = max(maxN, tmpMax);
                    }

                    tmpMax = 1;
                    for (int j = tmp.size() - 1; j >= 0; j--) {
                        tmpMax *= tmp[j];
                        maxN = max(maxN, tmpMax);
                    }
                } else {
                    for (int j = 0; j < tmp.size(); j++) {
                        tmpMax *= tmp[j];
                    }
                    maxN = max(maxN, tmpMax);
                }
                tmp.clear();
                zeroNums = 0;
            } else {
                if (i < 0) {
                    zeroNums++;
                }
                tmp.push_back(i);
            }
        }
        if (!tmp.empty()) {
            int tmpMax = 1;
            if (zeroNums % 2 == 1) {
                for (int j = 0; j < tmp.size(); j++) {
                    tmpMax *= tmp[j];
                    maxN = max(maxN, tmpMax);
                }
                tmpMax = 1;
                for (int j = tmp.size() - 1; j >= 0; j--) {
                    tmpMax *= tmp[j];
                    maxN = max(maxN, tmpMax);
                }
            } else {
                for (int j = 0; j < tmp.size(); j++) {
                    tmpMax *= tmp[j];
                }
                maxN = max(maxN, tmpMax);
            }
        }

        return maxN;
    }

    // 死亡翻滚
    int maxProduct2(vector<int> &nums) {
        int maxN = nums[0];
        int tmp = 1;
        int left = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                maxN = max(maxN, nums[i]);
                if (tmp < 0 && -tmp > maxN) {
                    while (left < i) {
                        if (tmp >= 0) {
                            maxN = max(maxN, tmp);
                            break;
                        }
                        if (nums[left] == 0) {
                            left++;
                            continue;
                        }
                        tmp /= nums[left];
                        left++;
                    }
                }
                tmp = 1;
                left = i + 1;
            } else {
                tmp *= nums[i];
                maxN = max(maxN, tmp);
            }
        }
        if (tmp < 0 && -tmp > maxN) {
            while (left < nums.size()) {
                if (tmp >= 0) {
                    maxN = max(maxN, tmp);
                    break;
                }
                tmp /= nums[left];
                left++;
            }
        }

        return maxN;
    }

    // 网上解法
    int maxProduct(vector<int> &nums) {
        /*int ans = nums[0];
        int m = nums[0], M = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int lastMin = m * nums[i];
            int lastMax = M * nums[i];
            m = min(nums[i], min(lastMin, lastMax));
            M = max(nums[i], max(lastMin, lastMax));
            ans = max(ans, M);
        }
        return ans;*/
        int minN = nums[0];
        int maxN = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int tmpMin = minN * nums[i];
            int tmpMax = maxN * nums[i];
            minN = min(nums[i], min(tmpMin, tmpMax));
            maxN = max(nums[i], max(tmpMin, tmpMax));
            res = max(maxN, res);
        }
        return res;
    }

};

int main() {
    Solution so;
    vector<int> nums = {2, 3, -2, 0, 4, -6, 0, 3, -1, -10};
    // m:3,M:6
    // m:-12,M:-2
    // m:-48,M:4
    // m:-24,M:288
    // m:-72,M:864
    // m:-864,M:72
    // m:-720,M:8640


    // m:3,M:6
    // m:-12,M:-2
    // m:0,M:0
    // m:0,M:4
    // m:-24,M:0
    // m:0,M:0
    // m:0,M:3
    // m:-3,M:0
    // m:-10,M:30
    int a = so.maxProduct(nums);
    cout << "res:" << a << endl;
    return 0;
}